package com.wwz.leetcode;

import com.wwz.common.ListNode;
import org.junit.Test;

public class Solution {


    @Test
    public void test() {
//        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
//        //ListNode listNode = reverseBetween(head, 1, 4);
//        ListNode end = head;
//        for (int i = 0; i < 4; i++) {
//            end = end.next;
//        }
        //ListNode listNode = reverse2(head, end);
        ListNode head = new ListNode(3, new ListNode(5,null));
        reverseBetween(head, 1, 2);
        //System.out.println(listNode);

    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 定位到start； pre表示start的前一个结点
        ListNode start = head, pre = null;
        for (int i = 1; i <= m - 1; i++) {
            pre = start;
            start = start.next;
        }
        // 定位到end, 为了不重复遍历，可以直接从start开始
        ListNode end = start;
        for (int i = 1; i <= n - m + 1; i++) {
            end = end.next;
        }
        // 反转 [start， end)
        ListNode reverseHead = reverse(start, end);
        // 正常情况
        if (pre != null) {
            pre.next = reverseHead;
            start.next = end;
            return head;
        }
        // m == 1时 pre=null
        else {
            start.next = end;
            return reverseHead;
        }
    }

    public ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null, next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}
